public class IsPalindrome {
    // leetcode 回文链表
    // https://leetcode.cn/problems/palindrome-linked-list/description/
    public boolean isPalindrome(ListNode head) {
        // 通过快慢指针找到链表的中间节点，然后将后半部分的链表进行逆序，比较两个链表是否相等
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode head2 = reverseList(slow);
        ListNode cur1 = head, cur2 = head2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val != cur2.val) return false;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode nextCur = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextCur;
        }
        return prev;
    }
}
